A known method of embedding auxiliary data as defined in the opening paragraph is disclosed in European Patent Application EP-A-0 359 325. In this prior-art method, embedding of the auxiliary data takes place in the original signal domain. Digitized audio samples or video pixels are modified so as to represent bits of an auxiliary data signal. Various examples of this modification are disclosed. One example is described in the introductory part of the patent application, viz. replacing the least significant bit of every n-th audio sample by an auxiliary data bit. Another example is replacing the least significant bit of every n-th sample by the exclusive OR of its most significant bit and an auxiliary data bit.
Nowadays, audio and video signals are often compressed prior to transmission and/or storage. Applying the prior art to such signals requires the compressed signal to be decoded and re-encoded. Not only is this an expensive operation, it is also unreliable because the auxiliary data information accommodated in the least significant bit of a signal sample may get lost in the compression stage.